//
//  main.cpp
//  模拟实现list
//
//  Created by 卜绎皓 on 2022/10/22.
//

#include<iostream>
#include<stdbool.h>
#include<assert.h>
using namespace std;


#pragma once

namespace byh
{
    template<class T>
    struct __list_node//一般前面使用__,表示给内部使用,为什么不使用内部类,因为不仅仅list要用它,迭代器也要用它(C++里还是比较少用内部类的)
    {
        __list_node<T>* _next;
        __list_node<T>* _prev;
        T _data;

        //这里支持无参的new Node,或者有参的new Node(x)
        __list_node(const T& x = T())
            : _next(nullptr)
            , _prev(nullptr)
            , _data(x)
        {}
    };

    //迭代器,用一个类去封装节点的指针,所以目前为止我们已知的迭代器的实现方式有两种:
    //a)原生指针(天然迭代器),它所指向的空间物理结构是连续的,也就是说只有string、vector才可以做天然迭代器(*就是当前位置的数据/++就是下一个位置/--就是下一个位置)
    //b)类(用一个类去封装原生指针,重载相关运算符,让这个类对象用起来像指针),它所指向的空间物理结构是不连续的(没有封装指针之前,*是结构体/++--的位置不明确)
    //iterator:<T, T&, T*>
    //const_iterator<T, const T&, const T*>
    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_iterator<T, Ref, Ptr> self;
        typedef __list_node<T> Node;
        Node* _node;

        __list_iterator(Node* node)
            : _node(node)
        {}

        //*it
        Ref operator*()
        {
            return _node->_data;
        }

        //
        Ptr operator->()
        {
            return     &_node->_data;
        }

        //++it
        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        //it++,tmp出了作用域销毁,传值返回,不能用引用
        self operator++(int)
        {
            //备份
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        //--it
        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        //it--
        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        //it+,它可以operator+(),但是效率很低,所以也就没有支持

        //lt.begin() != lt.end()
        bool operator!=(const self& it) const
        {
            return _node != it._node;
        }

        //lt.begin() == lt.end()
        bool operator==(const self& it) const
        {
            return _node == it._node;
        }
    };

    template<class T>
    class list
    {
        //这个不想让外面的人用,所以默认是私有的
        typedef __list_node<T> Node;
    public:
        //__list_iterator是什么名字并不重要,最终都会typedef为iterator,因为我们要用统一的方式去访问容器。比如vector<int>::iterator;你那个真正的迭代器是什么名称不重要
        //typedef __list_iterator<T> iterator;
        //typedef __list_const_iterator<T> const_iterator;
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;

        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);//最后一个节点的下一个位置,哨兵位
        }

        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }
        const_iterator end() const
        {
            return const_iterator(_head);
        }

        list()
        {
            //带头双向循环链表
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }
    
        //lt2(lt1)
        //传统写法
        /*list(const list<T>& lt)
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
            
            for(const auto& e : lt)
            {
                push_back(e);
            }
        }*/
        //现代写法,可以看到这里现代写法相比传统写法并没有讲到便宜,所以说现代写法也不一定是最优,需要灵活运用
        //它要先支持一个迭代器区间的才能写现代写法,同时这里支持其它容器的拷贝构造
        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        list(const list<T>& lt)
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            list<T> tmp(lt.begin(), lt.end());
            std::swap(_head, tmp._head);
        }
        
        //lt1 = lt2
        //传统写法
        /*list<T>& operator=(const list<T>& lt)
        {
            if(this != &lt)
            {
                clear();
                for(const auto& e : lt)
                {
                    push_back(e);
                }
            }
            return *this;
        }*/
        //现代写法,对于赋值有一个原则,深拷贝现代写法一定非常简单(只要写了拷贝构造,赋值就一定能用现代写法,并且很简洁)
        list<T>& operator=(list<T> lt)
        {
            swap(_head, lt._head);
            return *this;
        }
        
        //对于~list,先实现clear
        ~list()
        {
            clear();
            //清除头节点
            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            iterator it = begin();
            while(it != end())
            {
                //不清除头节点,直接复用
                it = erase(it);
            }
        }

        void push_back(const T& x)
        {
            //同insert(_head, x);,end()是最后节点的下一个位置_head
            insert(end(), x);
        }

        void push_front(const T& x)
        {
            //insert(_head->_next, x);,begin()是头节点的下一个位置
            insert(begin(), x);
        }

        void pop_back()
        {
            //同erase(_head->_prev);
            erase(--end());
        }

        void pop_front()
        {
            //同erase(_head->_next);
            erase(begin());
        }

        iterator insert(iterator pos, const T& x)
        {
            //备份;这里就体现了为啥我们在设计__list_node和__list_iterator时为什么是struct,如果用class,这里就得用友源,但没必要
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);

            //关联
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;

            //双向链表的insert是不会失效的,返回新插入的节点,这里同 __list_iterator<T> (newnode),且这里是一个匿名对象。
            return iterator(newnode);
            //同上,newnode是Node*(__list_node<T>)类型,而insert的返回类型是iterator(__list_iterator<T>)也可以,这是因为单参数的构造函数支持隐式类型转换,如 A aa = 1; 或 string s = "hello";。但因为不太明确,所以不太推荐
            //return newnode;
        }
        
        //虽然在外面调用list实例化了lt,但是list里面的函数编译器会按需实例化(外面调用了哪个成员函数,就实例化哪个)
        //erase不是模板?这里要注意类模板里的成员函数都是函数模板,erase的参数iterator就是typedef出来的模板
        iterator erase(iterator pos)
        {
            //空链表(只剩头节点)不能erase
            assert(pos != end());

            //备份
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            //释放
            delete cur;

            //关联
            prev->_next = next;
            next->_prev = prev;

            //返回删除元素之后的位置,注意这里的pos已经是野指针了
            return iterator(next);
        }

        size_t size()
        {
            size_t n = 0;
            iterator it = begin();
            while (it != end())
            {
                ++it;
                ++n;
            }
            return n;
        }

        bool empty()
        {
            return begin() == end();
        }
    private:
        Node* _head;
    };

    //const迭代器一般出现的场景是在传参的时候
    void print_list(const list<int>& l)
    {
        list<int>::const_iterator it = l.begin();
        while (it != l.end())
        {
            //*it += 2;//err,表达式必须是可修改的左值
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }

    void test_list1()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);

        print_list(lt);

        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
            *it *= 2;
            cout << *it << " ";
            ++it;
        }
        cout << endl;

        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;
    }
    
    struct TreeNode
    {
        struct TreeNode* _left;
        struct TreeNode* _right;
        int _val;

        TreeNode(int val = -1)
            : _left(nullptr)
            , _right(nullptr)
            , _val(val)
        {}
    };
    //ostream operator<<(ostream& TreeNode, TreeNode n){}
    
    void test_list2()
    {
        list<TreeNode> lt;
        lt.push_back(TreeNode(1));
        lt.push_back(TreeNode(2));
        lt.push_back(TreeNode(3));
        lt.push_back(TreeNode(4));

        list<TreeNode>::iterator it = lt.begin();
        while (it != lt.end())
        {
            //*it调operator*,返回_node->_data;,_data是T类型,而这的T是TreeNode,是一个结构体类型的树节点,而*it后是TreeNode,我们说了内置类型可以直接cout输出,但是自定义类型不行,所以我们可以operator<<,或者不用重载(使用结构体的特性)
            //cout << *it << " ";
            //有些场景不适合用cout
            //cout << (*it)._val << " ";
            //这是结构体的访问方式(结构体和指针的访问方式,细节如下说明 3. List item)
            printf("val:%d,left:%p,right:%p\n", (*it)._val, (*it)._left, (*it)._right);
            //像指针一样就要去重载->,[int* p   *p] [TreeNode* p     p->_val]
            printf("val:%d,left:%p,right:%p\n", it->_val, it->_left, it->_right);
            ++it;
        }
        cout << endl;
    }
    
    void test_list3()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        print_list(lt);
        
        lt.clear();
        
        lt.push_back(10);
        lt.push_back(20);
        lt.push_back(30);
        lt.push_back(40);
        print_list(lt);
    }
    
    void test_list4()
    {
        list<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        lt1.push_back(3);
        lt1.push_back(4);
        
        list<int> lt2(lt1);
        print_list(lt2);

        list<int> lt3(lt1.begin(), lt1.end());

        string s("hello");
        list<int> lt4(s.begin(), s.end());
    
        for (auto e : lt3)
        {
            cout << e << " ";
        }
        cout << endl;
        for (auto e : lt4)
        {
            cout << e << " ";
        }
        cout << endl;

        lt1 = lt4;
        for (auto e : lt1)
        {
            cout << e << " ";
        }
        cout << endl;
                                                                                                                                
    }
}





int main()
{
    byh::test_list1();
    byh::test_list2();
    byh::test_list3();
    byh::test_list4();
    return 0;
}
